COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00014 00003		At the Stanford AI Lab, the intent would be to have Corewar 
C00015 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn off "{"
.cb CORE WAR


	%2Core War%1 is a two-person competitive game played in
the memory of a computer.  The winner is the player who first sets
all locations in a disputed area to his player number.
The players create programs that try to destroy or subvert the
opponents programs and create further allied programs.
If %2core war%1 becomes popular, artificial intelligence may benefit,
because successful play will require very intelligent programs.

.bb General description

	Each player has his own display terminal on which are displayed
the contents of 100 registers of memory under his immediate control.  He
can also change the contents of these registers directly - as fast as he
can type.  He can change the contents of other registers, but the change
is not immediately effective, and he can do nothing else while he waits.
His programs can also display on his screen.

	There are 100 parallel processes each of which has a program
counter and some PDP-10 type accumulators.  An interpreter cycles
among these program counters, executing instructions in turn.
A slow instruction may be skipped a number of turns before it is finally
executed.  Initially 50 of these processes are executing "jump self"
instructions in each player's area.

	A player begins by typing in some programs.
Once a program is typed in he can start it going at some register by
modifying one of the "jump self" instructions.
Then he can type in another program and start it.

	His programs can write new programs and activate them by
modifying hitherto unused "jump self" instructions.
An obvious way a program can get another going is to copy itself
into new memory and activate the copy.

	The primary means of fighting is to capture the program
counters under the enemy's control.  Thus if one player stores
a jump instruction in the other's program that goes to a location
with a "jump self" in the attacker's domain, the attacker can
subsequently use that program counter.  A player with no programs
doing his will is helpless.

	An instruction that references memory takes an
amount of time proportional to the distance between
the instruction and the register referenced
unless there is a
%2barrier%1 word between the instruction
and the destination.  In that case, the instruction is not executed but
the location and type of the barrier encountered are stored in one oc
the process's accumulators.
Ordinary barriers can be created by storing into registers, and immovable
barriers existing when the game starts have the effect of defining terrain.
A barrier word has specified contents and
is not a legal instruction.

	The addressing of memory treats it as a one dimensional
array, but the distance function treats it as a rectangle
100 by 500 registers in size.  With respect to this geometry,
the distance is Euclidean.

	The basic language is a single address code with eight
general registers one of which is the program counter.  Each process
has its own general registers and program counter which are identified
with the first eight registers of the process and hence can be stored
into by an enemy trying to subvert the program or by a friendly program
supplying data.

	While the basic language is machine language, processes
may call read-only LISP subroutines.  These subroutines affect only a
specified area of
main memory and can return results only to the general registers
of the calling program or to the human's display.  Thus LISP can
be used for thinking but not for action.
Each player has a quota of LISP
memory and can write subroutines in it before the game starts.
The purpose of the LISP is to allow more elaborate strategies
than can be conveniently implemented in machine language.
The entry points to the LISP subroutines are in the player's home
area so his advance guards think more slowly than the generals at home.

	⊗Corewar is likely to want a lot of computer memory.  In order
to save memory, it is divided into blocks.  If there has been no
activity in a block in a long time, it reverts to a standard, briefly
described state, and the extra memory is garbage collected.


.bb The intellectual spirit of the game

	%2Corewar%1 is intended to be a game admitting very subtle
strategies with as much intelligence as the players can devise
and hopefully going beyond anything the designers of the game can
now imagine.  Should it turn out that a brute force strategy is effective
against all comers, the game should be changed.

	Effective strategies for the players are constrained by geometry.
Since a long distance store take a long time, and may encounter barriers,
it is not feasible to destroy the enemy by long range bombardment of
(storing into) his home territory.  Instead it is necessary to have
programs that will advance and bombard from close range.  Since an enemy
program that sneaks close can do a lot of damage, it is necessary to have
programs that scan as much territory as possible and mass firepower
against enemy programs that sneak close.

	Since a big program can be damaged by changing a single
instruction, it is important to check the integrity of a section of
program before entering it.  Of course, the enemy hopes to subvert a
location just before your program executes it, but his program can't
readily tell which locations will be active soon.  A program finding
itself seriously damaged should jump back to a home program, lest it be
subverted.

	If an enemy program can be inspected and understood, it can
perhaps be modified to sabotage the enemy undetected.  A side may
require commissar programs to check its other programs for orthodoxy.
Subverting a commissar may win big.

	The rules concerning the time required create barriers should
be designed so as to make them useful but not dominant.

	The terrain imposed by the initial barriers is unknown to the
players.  It may be explored by programs.

	Initially, we suppose that players will have to do all complex
thinking themselves.  Success will come from delegating more and more
complex tasks to the soldier programs.
If a player could make a general program more intelligent at core war
than himself, then he would have nothing further to do, since watching
the game wouldn't give him any good ideas of how to intervene.  This
is unlikely to occur in the near future.  Indeed it seems more likely
that for a long time to come, even inexperienced players will find
the initial routines created by corewar experts making mistakes that
intervention can correct.


.bb Spectators

	⊗Corewar can be a good spectator sport.  Registers are colored
according to the player who last affected them and also according to
who last looked at them and these colors fade with time.  When one
player stores into a program belonging to another and that instruction
is executed, then the subsequently executed instructions suddenly
change color.  The players will have similar maps describing the regions
they know about.
	At the Stanford AI Lab, the intent would be to have ⊗Corewar 
run in the PDP-11/45 with the zonker memory so as to not interfere
with the KL-10.  It would be a stand-alone program as far as the
PDP-11 is concerned and would be the lowest priority use of the PDP-11.
.skip 1
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of
COREWA[S77,JMC]
PUBbed at {time} on {date}.%1